package demo.practice.sort;

public class M1714 {


    public static void main(String[] args) {
        M1714 m1714=new M1714();
        m1714.smallestK(new int[]{1,3,5,7,2,4,6,8},5);
    }

    public int[] smallestK(int[] arr, int k) {
        mergeSort(arr, 0, arr.length - 1);
        int[] rt = new int[k];

        System.arraycopy(arr, 0, rt, 0, k);
        return rt;
    }

    private void mergeSort(int[] arr, int i, int j) {//
        if (i >= j)
            return;

        int mid = i + (j - i) / 2;
        mergeSort(arr, i, mid);
        mergeSort(arr, mid + 1, j);
        merge(arr, i, mid, j);
    }

    private void merge(int[] arr, int i, int mid, int j) {
        int[] combine = new int[j - i + 1];

        int m1=i;
        int m2=mid+1;
        for (int k = 0; k < combine.length /*&& m1<=mid&& m2<=j*/; k++) {
            //combine[k] = arr[m1]   >= arr[m2] || m1>=mid  ? arr[m2++] : arr[m1++];
            //if(m1>mid)

            combine[k] = m1>mid ? arr[m2++] : m2>j ? arr[m1++]:  arr[m1]   >= arr[m2]?  arr[m2++] : arr[m1++];

        }
        System.arraycopy(combine, 0, arr, i, j - i + 1);
    }
}
